/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode* newHead = new ListNode(0);
        newHead->next = head;
        ListNode *f = newHead, *s = newHead;
        while (f && f->next) {
            f = f->next->next;
            s = s->next;
            if (f == s) break;
        }
        if (f == nullptr || f->next == nullptr) return nullptr;

        unordered_set<ListNode*> book;
        book.insert(s);
        ListNode* cur = s->next;
        while (cur != s) {
            book.insert(cur);
            cur = cur->next;
        }

        f = head;
        while (book.find(f) == book.end()) 
            f = f->next;
        return f;
    }
};
